The Gaines Trace was a road in the Mississippi Territory. It was constructed in 1811 and 1812 from the Tennessee River (near Muscle Shoals) to Cotton Gin Port on the upper Tombigbee River and on to Fort Stoddert on the lower Tombigbee. The portion from the Tennessee River to Cotton Gin Port was surveyed in 1807 and 1808 by Edmund P. Gaines, the road's namesake.
The trace intersected Jackson's Military Road in Russellville, Alabama.